Subject: Re: QoS R - best route versus good enough route....

From: [email-masked] (Ariel Orda)
Date: Wed, 30 Apr 1997 15:18:33 +0300

Masataka,

MO>> The basic premise of both [CCS] and [MaSt] is that the complexity 
MO>> of computing paths that provide end-to-end delay guarantees can 
MO>> be reduced when certain types of schedulers are used in the network.
MO>
MO>The assumption is too strong that the algorithm is unusable
MO>after hierarchical aggregation when a single aggregated link
MO>actually consists of cascaded WFQ relays.

If what you are saying is that aggregation brings in additional
complexity, I could not agree more. Trying to get a handle on this
issue was what motivated (in part) the work of [GO96]. The result 
is that while there is clearly an increase in complexity because
of the *uncertainty* introduced by the aggregation process, it is
still possible to devise tractable solutions under relatively 
reasonable assumptions (see [GO96] for details).

MO>For example, the algorithm does not work if an ATM network is
MO>abstracted as a single link. But, don't bother to develop an
MO>integrated IP-ATM P.NNI, becasue the algorithm does not work
MO>with P.NNI aggregation, either.

Again, see [GO96] for some possible approaches on how to handle
such cases.

MO>> Here, 
MO>> it is important to note, as was pointed out by Qingming in a recent mail, 
MO>> that the assumption made in [CCS] on an a-priori fixed bandwidth value 
MO>
MO>Qingming made a mistake to think that a shortest path at certain rate
MO>is still the shortest path at a different rate and metric.

I don't think Qingming et al. made that mistake as they were computing 
shortest paths for all possible bandwidth values.

Ariel

---

From: Masataka Ohta <[email-masked]>
Date: Thu, 1 May 97 10:33:47 JST

Ariel;

> complexity, I could not agree more.

No.

The problem is that the aggregation makes a single aggregated
router have multiple internal hops.

That is, the assumption that "certain types of schedulers
are used in the network" is no longer valid.

> The result 

It's not uncertainity, at all.

Aggregation naturally brings in inaccuracy, which is unavoidable
but NOT a problem here.

> Again, see [GO96] for some possible approaches on how to handle

Of course, it may not be impossible to approximate any scheduler
used with P.NNI consists of integral number of cascaded WFQ-type
schedulers and have some approximated algorithm which have
complexity polynominal to N, where N is the number of all the
cascaded WFQs.

But, it is just yet another approximation algorithm and N could be
very large to be impractical.

> shortest paths for all possible bandwidth values.

Qingming successfully showed a way to know an existence of a path
to satisfy QoS requirement.

As long as you use the bandwidth actually used for the computation,
yes, the path found is optimal w.r.t. the bandwidth.

But, as we use minimal bandwidth to satisfy the requirement,
the once-shortest path may not be the shortest (shortest delay,
for example) with reduced bandwidth and modified cost function.

						Masataka Ohta